package com.lun.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;



/**
 * 
 * N叉树
 * 
 * @author abc
 *
 */
public class NAryTree {
	
	public static class Node {
	    public int val;
	    public List<Node> children;//注意，约定值为null或size >= 1的List，不能为size为0的List

	    public Node() {}

	    public Node(int _val) {
	        val = _val;
	    }

	    public Node(int _val, List<Node> _children) {
	        val = _val;
	        children = _children;
	    }
	}
	
	public static Node integersToNAryTree(Integer... ints) {
		if(ints == null || ints.length == 0 || ints[0] == null)
			return null;
		LinkedList<Node> queue = new LinkedList<>();
		Node root = n(ints[0]);
		
		if(ints[1] != null) 
			throw new RuntimeException("The second argument should be null.");
		
		queue.offer(root);
		
		List<Node> children = new ArrayList<>(); 
		for(int i = 2; i <= ints.length; i++) {
			if(i == ints.length || ints[i] == null) {
				Node node = queue.poll();
				if(children.size() == 0) continue;
				node.children = children;
				queue.addAll(children);
				children = new ArrayList<>();
			}else {
				children.add(n(ints[i]));
			}
		}
		
		return root;
	}
	
	
	public static boolean equals(Node root1, Node root2) {
		
		if(root1 == null ^ root2 == null) {
			return false;
		}
		
		if(root1 != null && root2 != null) {
			if(root1.val != root2.val)
				return false;
			
			if(root1.children == null && root2.children == null) {
				return true;
			}else if(root1.children == null ^ root2.children == null) {
				return false;
			}else {
				int size = root1.children.size();
				if(size != root2.children.size())
					return false;
				
				for(int i = 0; i < size; i++) {
					boolean result = equals(root1.children.get(i), root2.children.get(i));
					if(!result) return false;
				}
			}
		}
		
		return true;
	}
	
	
	//创建节点的方便工具方法
	
	public static Node n(int n) {
		return new Node(n);
	}
	
	public static Node n(int n, List<Node> children) {
		return new Node(n, children);
	}
	
	@SuppressWarnings("unchecked")
	public static <T> List<T> al(T... a){
		return Arrays.asList(a);
	}
	
}
